home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / libqbuild / vis.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-15  |  42.1 KB  |  1,565 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. int bitbytes;                            /* (num_visleafs+63)>>3 */
  5. int bitlongs;
  6. int c_chains;
  7. int c_leafsee, c_portalsee;
  8. int c_portalskip, c_leafskip;
  9. int c_portaltest, c_portalpass, c_portalcheck;
  10. int c_vistest, c_mighttest;
  11. int count_sep;
  12. int leafon;                            /* the next leaf to be given to a thread to process */
  13. int originalvismapsize;
  14. int testvislevel = 2;
  15. int testvisfastlevel = 3;
  16. int totalvis;
  17. unsigned char *uncompressed;                    /* [bitbytes*num_visleafs] */
  18.  
  19. /*
  20.  * These variables are used by both BasePortalVis and SimpleFlood.
  21.  * portalsee is an array of bytes. When running BasePortalVis,
  22.  * the array is filled with a 'mightsee' indicator
  23.  * c_* is counters.
  24.  */
  25. unsigned char portalsee[MAX_MAP_PORTALS];
  26.  
  27. void CheckStack(register struct visleaf *leaf, register threaddata_t * thread)
  28. {
  29.   pstack_t *p;
  30.  
  31.   for (p = thread->pstack_head.next; p; p = p->next)
  32.     if (p->leaf == leaf)
  33.       Error("CheckStack: leaf recursion");
  34. }
  35.  
  36. /*
  37.  * ==============
  38.  * ClipToSeperators
  39.  * 
  40.  * Source, pass, and target are an ordering of portals.
  41.  * 
  42.  * Generates seperating planes canidates by taking two points from source and one
  43.  * point from pass, and clips target by them.
  44.  * 
  45.  * If target is totally clipped away, that portal can not be seen through.
  46.  * 
  47.  * Normal clip keeps target on the same side as pass, which is correct if the
  48.  * order goes source, pass, target.  If the order goes pass, source, target then
  49.  * flipclip should be set.
  50.  * ==============
  51.  */
  52. #ifndef NEWVIS
  53. struct winding *ClipToSeperators(register struct winding *source, register struct winding *pass, register struct winding *target, register bool flipclip)
  54. {
  55.   int i, j, k, l;
  56.   struct plane plane;
  57.   vec3_t v1, v2;
  58.   float d;
  59.   vec_t length;
  60.   int counts[3];
  61.   bool fliptest;
  62.  
  63.   /* check all combinations        */
  64.   for (i = 0; i < source->numpoints; i++) {
  65.     l = (i + 1) % source->numpoints;
  66.     VectorSubtract(source->points[l], source->points[i], v1);
  67.  
  68.     /*
  69.      * fing a vertex of pass that makes a plane that puts all of the
  70.      * vertexes of pass on the front side and all of the vertexes of
  71.      * source on the back side
  72.      */
  73.     for (j = 0; j < pass->numpoints; j++) {
  74.       VectorSubtract(pass->points[j], source->points[i], v2);
  75.  
  76.       plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
  77.       plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
  78.       plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
  79.  
  80.       /* if points don't make a valid plane, skip it */
  81.       length = plane.normal[0] * plane.normal[0]
  82.     + plane.normal[1] * plane.normal[1]
  83.     + plane.normal[2] * plane.normal[2];
  84.  
  85.       if (length < ON_EPSILON)
  86.     continue;
  87.  
  88.       length = 1 / sqrt(length);
  89.  
  90.       plane.normal[0] *= length;
  91.       plane.normal[1] *= length;
  92.       plane.normal[2] *= length;
  93.  
  94.       plane.dist = DotProduct(pass->points[j], plane.normal);
  95.  
  96.       /*
  97.        * find out which side of the generated seperating plane has the
  98.        * source portal
  99.        */
  100.       fliptest = FALSE;
  101.       for (k = 0; k < source->numpoints; k++) {
  102.     if (k == i || k == l)
  103.       continue;
  104.     d = DotProduct(source->points[k], plane.normal) - plane.dist;
  105.     if (d < -ON_EPSILON) {                    /* source is on the negative side, so we want all */
  106.       /* pass and target on the positive side */
  107.       fliptest = FALSE;
  108.       break;
  109.     }
  110.     else if (d > ON_EPSILON) {                /* source is on the positive side, so we want all */
  111.       /* pass and target on the negative side */
  112.       fliptest = TRUE;
  113.       break;
  114.     }
  115.       }
  116.       if (k == source->numpoints)
  117.     continue;                        /* planar with source portal */
  118.  
  119.       /* flip the normal if the source portal is backwards */
  120.       if (fliptest) {
  121.     VectorNegate(plane.normal);
  122.     plane.dist = -plane.dist;
  123.       }
  124.  
  125.       /*
  126.        * if all of the pass portal points are now on the positive side,
  127.        * this is the seperating plane
  128.        */
  129.       counts[0] = counts[1] = counts[2] = 0;
  130.       for (k = 0; k < pass->numpoints; k++) {
  131.     if (k == j)
  132.       continue;
  133.     d = DotProduct(pass->points[k], plane.normal) - plane.dist;
  134.     if (d < -ON_EPSILON)
  135.       break;
  136.     else if (d > ON_EPSILON)
  137.       counts[0]++;
  138.     else
  139.       counts[2]++;
  140.       }
  141.       if (k != pass->numpoints)
  142.     continue;                        /* points on negative side, not a seperating plane */
  143.  
  144.       if (!counts[0]) {
  145.     continue;                        /* planar with seperating plane */
  146.  
  147.       }
  148.  
  149.       /* flip the normal if we want the back side */
  150.       if (flipclip) {
  151.     VectorNegate(plane.normal);
  152.     plane.dist = -plane.dist;
  153.       }
  154.  
  155.       /* clip target by the seperating plane */
  156.       target = ClipWinding(target, &plane, FALSE);
  157.       if (!target)
  158.     return NULL;                        /* target is not visible */
  159.  
  160.     }
  161.   }
  162.  
  163.   return target;
  164. }
  165. #else
  166. struct winding *ClipToSeperators(struct winding *SourceWinding, struct winding *PassWinding,
  167.                  struct winding *TargetWinding, bool flipclip)
  168. {
  169.   int i, j, k, l;
  170.  
  171.   struct plane ClipPlane;
  172.   vec3_t v1, v2;
  173.   float d;
  174.   double length;
  175.  
  176.   bool ContFlag;
  177.   bool fliptest;
  178.  
  179.   /*
  180.    * Zero'th idea: Only one j point can make a candidate plane. (RVis).
  181.    *
  182.    * First idea: A good candidate for the next point, would be the same
  183.    * point. ::: Didn't show up as an improvement.
  184.    *
  185.    * Second idea: If one combination of the points gives a planar test
  186.    * agains the source portal, all points will (approximatly. Some might
  187.    * not (the ON_EPSILON 'error'), but the planes constructed from this
  188.    * is either behind the PassWinding (and will therefore not interfere with
  189.    * the TargetWinding), or on the same side of PassWinding as the SourceWinding.
  190.    * (In the last case, the plane will be rejected in any case).
  191.    * I don't know if this logic is OK....
  192.    * :::: Very very bad idea. Time went up, correctness went down.
  193.    * Logic must have been broke....
  194.    */
  195.  
  196.   /* check all combinations */
  197.   for (i = 0; i < SourceWinding->numpoints; i++) {
  198.     l = (i + 1) % SourceWinding->numpoints;
  199.     /* We now have two points. Make a vector from them. (v1). */
  200.     VectorSubtract(SourceWinding->points[l], SourceWinding->points[i], v1);
  201.  
  202.     /*
  203.      * Find a vertex of PassWinding that makes a ClipPlane that puts all of the
  204.      * vertexes of PassWinding on the front side and all of the vertexes of
  205.      * SourceWinding on the back side
  206.      */
  207.     for (j = 0; (j < PassWinding->numpoints); j++) {
  208.       /* Set j. Overflow rightly. */
  209.       /*      j = (Next + Count)%PassWinding->numpoints; */
  210.  
  211.       /*
  212.        * Make another vector from one point, and this point.
  213.        * The two vectors now defines a plane. 
  214.        */
  215.       VectorSubtract(PassWinding->points[j], SourceWinding->points[i], v2);
  216.  
  217.       /* Define a plane normal, with the crossproduct. */
  218.       ClipPlane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
  219.       ClipPlane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
  220.       ClipPlane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
  221.  
  222.       /*
  223.        * if points don't make a valid ClipPlane, skip it
  224.        * Get the normals lenght
  225.        */
  226.       length = ClipPlane.normal[0] * ClipPlane.normal[0]
  227.     + ClipPlane.normal[1] * ClipPlane.normal[1]
  228.     + ClipPlane.normal[2] * ClipPlane.normal[2];
  229.       /* If too small, skip it. */
  230.       if (length < ON_EPSILON)
  231.     continue;
  232.  
  233.       /* Normalize the plane. */
  234.       length = 1 / sqrt(length);
  235.       ClipPlane.normal[0] *= length;
  236.       ClipPlane.normal[1] *= length;
  237.       ClipPlane.normal[2] *= length;
  238.  
  239.       ClipPlane.dist = DotProduct(PassWinding->points[j], ClipPlane.normal);
  240.  
  241.       /*
  242.        * find out which side of the generated seperating ClipPlane has the
  243.        * SourceWinding portal
  244.        */
  245.       fliptest = FALSE;
  246.       for (k = 0; k < SourceWinding->numpoints; k++) {
  247.     if (k == i || k == l)
  248.       continue;
  249.     d = DotProduct(SourceWinding->points[k], ClipPlane.normal) - ClipPlane.dist;
  250.     if (d < -ON_EPSILON) {                    /* SourceWinding is on the negative side, so we want all */
  251.       /* PassWinding and TargetWinding on the positive side */
  252.       fliptest = FALSE;
  253.       break;
  254.     }
  255.     else if (d > ON_EPSILON) {                /* SourceWinding is on the positive side, so we want all */
  256.       /* PassWinding and TargetWinding on the negative side */
  257.       fliptest = TRUE;
  258.       break;
  259.     }
  260.       }
  261.       if (k == SourceWinding->numpoints)
  262.     continue;                        /* planar with SourceWinding portal */
  263.  
  264.       /* flip the normal if the SourceWinding portal is backwards */
  265.       if (fliptest) {
  266.     VectorSubtract(vec3_origin, ClipPlane.normal, ClipPlane.normal);
  267.     ClipPlane.dist = -ClipPlane.dist;
  268.       }
  269.  
  270.       /*
  271.        * if all of the PassWinding portal points are now on the positive side,
  272.        * this is the seperating ClipPlane
  273.        *
  274.        * We want t0 calculate further, if no points behind, and at least one in front
  275.        */
  276.       ContFlag = TRUE;
  277.  
  278.       for (k = 0; k < PassWinding->numpoints; k++) {
  279.     if (k == j)
  280.       continue;
  281.     d = DotProduct(PassWinding->points[k], ClipPlane.normal) - ClipPlane.dist;
  282.     if (d < -ON_EPSILON) {
  283.       ContFlag = TRUE;
  284.       break;
  285.     }
  286.     /* If at least one point is above the plane, then */
  287.     /* we can calculate. */
  288.     else if (d > ON_EPSILON) {
  289.       ContFlag = FALSE;
  290.     }
  291.       }
  292.       /*
  293.        * We want to calculate further, if
  294.        * a) No points with d < -ON_EPSILON
  295.        * b) At least one point with non planar.
  296.        */
  297.       if (ContFlag)
  298.     continue;
  299.  
  300.       /* flip the normal if we want the back side */
  301.       if (flipclip) {
  302.     VectorSubtract(vec3_origin, ClipPlane.normal, ClipPlane.normal);
  303.     ClipPlane.dist = -ClipPlane.dist;
  304.       }
  305.  
  306.       /* clip TargetWinding by the seperating ClipPlane */
  307.       TargetWinding = ClipWinding(TargetWinding, &ClipPlane, FALSE);
  308.       if (!TargetWinding)
  309.     return NULL;                        /* TargetWinding is not visible */
  310.       /* RVIS modification.
  311.        *
  312.        * Observation:
  313.        * For any given vector, beeing part of the SourceWinding, at most
  314.        * one point in PassWinding, together with the vector, defines a uniqe
  315.        * plane with all points of SourceWinding on one side, and all
  316.        * points of PassWinding at the other.
  317.        * There may be other points, that fullfill the criteria, but
  318.        * the plane generated will be the same.
  319.        * Therefore, further search is fruitless.
  320.        */
  321.       break;
  322.     }                                /* j For loop. */
  323.   }                                /* i for loop */
  324.   return TargetWinding;
  325. }
  326. #endif
  327.  
  328. /*
  329.  * ==================
  330.  * RecursiveLeafFlow
  331.  * 
  332.  * Flood fill through the leafs
  333.  * If src_portal is NULL, this is the originating leaf
  334.  * ==================
  335.  *
  336.  * Called from PortalFlow.
  337.  * This is a huge procedure, and probably the one that contains all the meat
  338.  * of the program.
  339.  * In here, the testlevel parameter is used.
  340.  * ClipToSeperators are called testlevel times, with different parameters.
  341.  */
  342. void RecursiveLeafFlow(register int leafnum, register threaddata_t * thread, register pstack_t * prevstack)
  343. {
  344.   pstack_t stack;
  345.   struct visportal *p;
  346.   struct plane backplane;
  347.   struct winding *source, *target;
  348.   struct visleaf *leaf;
  349.   int i, j;
  350.  
  351.   /*
  352.    * only on some systems "long int" is 64bits,
  353.    * but on all "long long int" is 64bits
  354.    */
  355.   long long int *test, *might, *vis;
  356.   bool more;
  357.  
  358.   c_chains++;
  359.  
  360.   leaf = leafs[leafnum];
  361.   CheckStack(leaf, thread);
  362.  
  363.   /* mark the leaf as visible */
  364.   if (!(thread->leafvis[leafnum >> 3] & (1 << (leafnum & 7)))) {
  365.     thread->leafvis[leafnum >> 3] |= 1 << (leafnum & 7);
  366.     thread->base->numcansee++;
  367.   }
  368.  
  369.   prevstack->next = &stack;
  370.   stack.next = NULL;
  371.   stack.leaf = leaf;
  372.   stack.portal = NULL;
  373.   if (!(stack.mightsee = (unsigned char *)tmalloc(bitbytes)))
  374.     Error(failed_memoryunsize, "bitbytes");
  375.   might = (long long int *)stack.mightsee;
  376.   vis = (long long int *)thread->leafvis;
  377.  
  378.   /* check all portals for flowing into other leafs        */
  379.   for (i = 0; i < leaf->numportals; i++) {
  380.     p = leaf->portals[i];
  381.  
  382.     if (!(prevstack->mightsee[p->leaf >> 3] & (1 << (p->leaf & 7)))) {
  383.       c_leafskip++;
  384.       continue;                            /* can't possibly see it */
  385.  
  386.     }
  387.  
  388.     /* if the portal can't see anything we haven't allready seen, skip it */
  389.     if (p->status == stat_done) {
  390.       c_vistest++;
  391.       test = (long long int *)p->visbits;
  392.     }
  393.     else {
  394.       c_mighttest++;
  395.       test = (long long int *)p->mightsee;
  396.     }
  397.     more = FALSE;
  398.     for (j = 0; j < bitlongs; j++) {
  399.       might[j] = ((long long int *)prevstack->mightsee)[j] & test[j];
  400.       if (might[j] & ~vis[j])
  401.     more = TRUE;
  402.     }
  403.  
  404.     if (!more) {                        /* can't see anything new */
  405.  
  406.       c_portalskip++;
  407.       continue;
  408.     }
  409.  
  410.     /* get plane of portal, point normal into the neighbor leaf */
  411.     stack.portalplane = p->plane;
  412.     VectorNegateTo(p->plane.normal, backplane.normal);
  413.     backplane.dist = -p->plane.dist;
  414.  
  415.     if (VectorCompare(prevstack->portalplane.normal, backplane.normal))
  416.       continue;                            /* can't go out a coplanar face */
  417.  
  418.     c_portalcheck++;
  419.  
  420.     stack.portal = p;
  421.     stack.next = NULL;
  422.  
  423.     target = ClipWinding(p->winding, &thread->pstack_head.portalplane, FALSE);
  424.     if (!target)
  425.       continue;
  426.  
  427.     if (!prevstack->pass) {                    /* the second leaf can only be blocked if coplanar */
  428.       stack.source = prevstack->source;
  429.       stack.pass = target;
  430.       RecursiveLeafFlow(p->leaf, thread, &stack);
  431.       FreeWinding(target);
  432.       continue;
  433.     }
  434.  
  435.     target = ClipWinding(target, &prevstack->portalplane, FALSE);
  436.     if (!target)
  437.       continue;
  438.  
  439.     source = CopyWinding(prevstack->source);
  440.     source = ClipWinding(source, &backplane, FALSE);
  441.     if (!source) {
  442.       FreeWinding(target);
  443.       continue;
  444.     }
  445.  
  446.     c_portaltest++;
  447.  
  448.     if (testvislevel > 0) {
  449.       target = ClipToSeperators(source, prevstack->pass, target, FALSE);
  450.       if (!target) {
  451.     FreeWinding(source);
  452.     continue;
  453.       }
  454.     }
  455.  
  456.     if (testvislevel > 1) {
  457.       target = ClipToSeperators(prevstack->pass, source, target, TRUE);
  458.       if (!target) {
  459.     FreeWinding(source);
  460.     continue;
  461.       }
  462.     }
  463.  
  464.     if (testvislevel > 2) {
  465.       source = ClipToSeperators(target, prevstack->pass, source, FALSE);
  466.       if (!source) {
  467.     FreeWinding(target);
  468.     continue;
  469.       }
  470.     }
  471.  
  472.     if (testvislevel > 3) {
  473.       source = ClipToSeperators(prevstack->pass, target, source, TRUE);
  474.       if (!source) {
  475.     FreeWinding(target);
  476.     continue;
  477.       }
  478.     }
  479.  
  480.     /*
  481.      * The reason why, this level, and > 3 is beeing run, is because "non-aligned"
  482.      * portals will generate different planes
  483.      * This also means, that "aligned" portals, need not run this.
  484.      * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  485.      * Since a great deal IS aligned, it might be worth trying!!!
  486.      */
  487.     stack.source = source;
  488.     stack.pass = target;
  489.  
  490.     c_portalpass++;
  491.  
  492.     /* flow through it for real */
  493.     RecursiveLeafFlow(p->leaf, thread, &stack);
  494.  
  495.     FreeWinding(source);
  496.     FreeWinding(target);
  497.   }
  498.  
  499.   tfree(stack.mightsee);
  500. }
  501.  
  502. /*
  503.  * ===============
  504.  * PortalFlow
  505.  * 
  506.  * ===============
  507.  */
  508. void PortalFlow(register struct visportal *p)
  509. {
  510.   threaddata_t data;
  511.  
  512.   if (p->status != stat_working)
  513.     Error("PortalFlow: reflowed\n");
  514.   p->status = stat_working;
  515.  
  516.   if (!(p->visbits = (unsigned char *)kmalloc(bitbytes)))
  517.     Error(failed_memoryunsize, "bitbytes");
  518.  
  519.   __bzero(&data, sizeof(data));
  520.   data.leafvis = p->visbits;
  521.   data.base = p;
  522.  
  523.   data.pstack_head.portal = p;
  524.   data.pstack_head.source = p->winding;
  525.   data.pstack_head.portalplane = p->plane;
  526.   data.pstack_head.mightsee = p->mightsee;
  527.  
  528.   RecursiveLeafFlow(p->leaf, &data, &data.pstack_head);
  529.  
  530.   p->status = stat_done;
  531. }
  532.  
  533. /*
  534.  * ===============================================================================
  535.  * This is a rough first-order aproximation that is used to trivially reject some
  536.  * of the final calculations.
  537.  * ===============================================================================
  538.  *
  539.  * This procedure flows out of a source leaf entering from portal scrportal.
  540.  * First, the portal's mightsee array is set to 1, for the leafnum leaf
  541.  * Then, for each portal leaving the leaf, it is checked if the srcportal can see
  542.  * this portal. If that is the case, the procedure is called recursively.
  543.  */
  544.  
  545. void SimpleFlood(register struct visportal *srcportal, register int leafnum)
  546. {
  547.   int i;
  548.   struct visleaf *leaf;
  549.   struct visportal *p;
  550.  
  551.   /* Catchs circular references. */
  552.   if (srcportal->mightsee[leafnum >> 3] & (1 << (leafnum & 7)))
  553.     return;
  554.   /* Set the current leaf to visible. */
  555.   srcportal->mightsee[leafnum >> 3] |= (1 << (leafnum & 7));
  556.   c_leafsee++;
  557.  
  558.   /* Get the portals leaving this leaf. */
  559.   leaf = leafs[leafnum];
  560.  
  561.   /* Check each portal away from leaf */
  562.   for (i = 0; i < leaf->numportals; i++) {
  563.     p = leaf->portals[i];
  564.     /* If the portal is visible from srcportal */
  565.     if (!portalsee[p - portals])
  566.       continue;
  567.     /* then call recursivly. */
  568.     SimpleFlood(srcportal, p->leaf);
  569.   }
  570. }
  571.  
  572. /*
  573.  * ==============
  574.  * BasePortalVis
  575.  * ==============
  576.  * 
  577.  * It performs a trivial reject of some portal connections.
  578.  * The criteria is, that one portal has to be able to look through, in the
  579.  * loosest sense, another portal.
  580.  * In effect, this means, that portal b need to be in front of a, and portal
  581.  * a need to be behind b.
  582.  */
  583. #ifndef NEWVIS
  584. #define    BasePortalVis_1 BasePortalVis
  585. #define    BasePortalVis_2 BasePortalVis
  586. #define    BasePortalVis_3 BasePortalVis
  587. #define    BasePortalVis_4 BasePortalVis
  588. void BasePortalVis(void)
  589. {
  590.   int i, j, k;
  591.   struct visportal *tp, *p;
  592.   float d;
  593.   struct winding *w;
  594.  
  595.   for (i = 0, p = portals; i < num_visportals * 2; i++, p++) {
  596.     if (!(p->mightsee = (unsigned char *)kmalloc(bitbytes)))
  597.       Error(failed_memoryunsize, "bitbytes");
  598.     c_portalsee = 0;
  599.     __bzero(portalsee, num_visportals * 2);
  600.  
  601.     for (j = 0, tp = portals; j < num_visportals * 2; j++, tp++) {
  602.       if (j == i)
  603.     continue;
  604.       w = tp->winding;
  605.       for (k = 0; k < w->numpoints; k++) {
  606.     d = DotProduct(w->points[k], p->plane.normal) - p->plane.dist;
  607.     if (d > ON_EPSILON)
  608.       break;
  609.       }
  610.       if (k == w->numpoints)
  611.     continue;                        /* no points on front */
  612.  
  613.       w = p->winding;
  614.       for (k = 0; k < w->numpoints; k++) {
  615.     d = DotProduct(w->points[k], tp->plane.normal) - tp->plane.dist;
  616.     if (d < -ON_EPSILON)
  617.       break;
  618.       }
  619.       if (k == w->numpoints)
  620.     continue;                        /* no points on front */
  621.  
  622.       portalsee[j] = 1;
  623.       c_portalsee++;
  624.  
  625.     }
  626.  
  627.     c_leafsee = 0;
  628.     SimpleFlood(p, p->leaf);
  629.     p->nummightsee = c_leafsee;
  630.   }
  631. }
  632. #else
  633. /*
  634.  * PortalFrontPortal returns true if at least one of the points of TestPortals
  635.  * windings is in front if SourcePortal
  636.  */
  637. bool PortalFrontBackPortal_3(struct visportal *SourcePortal, struct visportal *TestPortal)
  638. {
  639.   int i;
  640.   float d;
  641.   struct winding *Winding;
  642.  
  643.   /* Test front */
  644.   Winding = TestPortal->winding;
  645.   for (i = 0; i < Winding->numpoints; i++) {
  646.     d = DotProduct(Winding->points[i], SourcePortal->plane.normal)
  647.       - SourcePortal->plane.dist;
  648.     if (d > ON_EPSILON)                        /* Test if back */
  649.       break;
  650.   }
  651.   if (i == Winding->numpoints)
  652.     return FALSE;
  653.   /* Test back */
  654.   Winding = SourcePortal->winding;
  655.   for (i = 0; i < Winding->numpoints; i++) {
  656.     d = DotProduct(Winding->points[i], TestPortal->plane.normal)
  657.       - TestPortal->plane.dist;
  658.     if (d < -ON_EPSILON)
  659.       return TRUE;
  660.   }
  661.   return FALSE;
  662. }                                /* PortalFrontPortal */
  663.  
  664. /*
  665.  * 4:
  666.  * This version of BasePortalVis uses a DFS approach to find the
  667.  * mightsee set.
  668.  * Besides that, it also uses a stronger test-criterium to lower
  669.  * the upper limit recorded in the mightsee set.
  670.  */
  671. /* For now; allocate a hell of a lot of pointers; */
  672.  
  673. struct visportal *ThroughPortals[MAX_MAP_PORTALS];
  674. int ThroughCount;
  675.  
  676. /* Returns true, if NOT in array. */
  677. bool PortalCircularCheck(struct visportal *TestPortal)
  678. {
  679.   int k;
  680.  
  681.   for (k = 0; k < ThroughCount; k++)
  682.     if (ThroughPortals[k] == TestPortal)
  683.       return FALSE;
  684.   return TRUE;
  685. }
  686.  
  687. /* Test TestPortal with all portals in ThroughPortals */
  688. bool PortalThroughPortals_4(struct visportal * TestPortal)
  689. {
  690.   int k;
  691.  
  692.   for (k = 0; k < ThroughCount; k++)
  693.     if (!(PortalFrontBackPortal_3(ThroughPortals[k], TestPortal)))
  694.       return FALSE;
  695.   return TRUE;
  696. }
  697.  
  698. /*
  699.  * PortalThroughLeaf_4 returns TRUE, IF all portals leaving leafnum,
  700.  * does not fullfill the standard test criterium.
  701.  */
  702. void PortalThroughLeaf_4(int leafnum, bool LastOut)
  703. {
  704.   int i;
  705.  
  706.   struct visleaf *leaf;
  707.   struct visportal *TestPortal;
  708.   bool IsLast;
  709.  
  710.   /* Catchs circular references. */
  711.   if (ThroughPortals[0]->mightsee[leafnum >> 3] & (1 << (leafnum & 7)))
  712.     return;
  713.   /* Set the current leaf to visible. */
  714.   ThroughPortals[0]->mightsee[leafnum >> 3] |= (1 << (leafnum & 7));
  715.   c_leafsee++;
  716.   /* Get the portals leaving this leaf. */
  717.   leaf = &leafs[leafnum];
  718.   for (i = 0; i < leaf->numportals; i++) {            /* Check each portal away from leaf */
  719.     TestPortal = leaf->portals[i];
  720.     if (LastOut) {                        /* Can use strict testing. */
  721.       if (PortalThroughPortals_4(TestPortal)) {
  722.     if (i == (leaf->numportals - 1))
  723.       IsLast = TRUE;
  724.     else
  725.       IsLast = FALSE;
  726.     ThroughPortals[ThroughCount++] = TestPortal;
  727.     PortalThroughLeaf_4(TestPortal->leaf, IsLast);        /* then call recursivly. */
  728.     ThroughCount--;
  729.       }
  730.     }
  731.     else {                            /* Can not use strict testing. */
  732.       if (PortalFrontBackPortal_3(ThroughPortals[0], TestPortal)) {
  733.     ThroughPortals[ThroughCount++] = TestPortal;
  734.     PortalThroughLeaf_4(TestPortal->leaf, FALSE);
  735.     ThroughCount--;
  736.       }
  737.     }
  738.   }                                /* For each portal */
  739. }                                /* PortalThroughLeaf(...) */
  740.  
  741. /* Simply call PortalFollowPortals for each portal. */
  742. void BasePortalVis_4(void)
  743. {
  744.   int i;
  745.   struct visportal *SourcePortal;
  746.  
  747.   /* For each portal            repeat */
  748.   for (i = 0, SourcePortal = portals; i < numportals * 2; i++, SourcePortal++) {
  749.     /* Allocate memory to the mightsee array */
  750.     SourcePortal->mightsee = kmalloc(bitbytes);
  751.     __bzero(SourcePortal->mightsee, bitbytes);
  752.     /* SimpleFloof tags all the leafs, that SourcePortal might see. */
  753.     ThroughPortals[0] = SourcePortal;
  754.     ThroughCount = 1;
  755.     c_leafsee = 0;
  756.     PortalThroughLeaf_4(SourcePortal->leaf, TRUE);
  757.     SourcePortal->nummightsee = c_leafsee;
  758.   }                                /* For each portal */
  759. }
  760.  
  761. /*
  762.  * 3:
  763.  * This version of BasePortalVis uses a DFS approach to find the
  764.  * mightsee set.
  765.  * It thereby hopes, that it can perform fewer calculations than
  766.  * the standard version. It could result in -worse- performance,
  767.  * but so far, it has been running in 35-55% of original time.
  768.  * It uses a helper funtion, that appears first:
  769.  */
  770. void PortalThroughLeaf_3(struct visportal *SourcePortal, int leafnum)
  771. {
  772.   int i;
  773.   struct visleaf *leaf;
  774.   struct visportal *TestPortal;
  775.  
  776.   /* Catchs circular references. */
  777.   if (SourcePortal->mightsee[leafnum >> 3] & (1 << (leafnum & 7)))
  778.     return;
  779.   /* Set the current leaf to visible. */
  780.   SourcePortal->mightsee[leafnum >> 3] |= (1 << (leafnum & 7));
  781.   c_leafsee++;
  782.   /* Get the portals leaving this leaf. */
  783.   leaf = &leafs[leafnum];
  784.   for (i = 0; i < leaf->numportals; i++) {            /* Check each portal away from leaf */
  785.     TestPortal = leaf->portals[i];
  786.     if (PortalFrontBackPortal_3(SourcePortal, TestPortal))
  787.       PortalThroughLeaf_3(SourcePortal, TestPortal->leaf);    /* then call recursivly. */
  788.   }
  789. }                                /* PortalThroughLeaf(...) */
  790.  
  791. /* Simply call PortalFollowPortals for each portal. */
  792. void BasePortalVis_3(void)
  793. {
  794.   int i;
  795.   struct visportal *SourcePortal;                /*, EndPortal; */
  796.  
  797.   /* For each portal            repeat */
  798.   for (i = 0, SourcePortal = portals; i < numportals * 2; i++, SourcePortal++) {
  799.     /* Allocate memory to the mightsee array */
  800.     SourcePortal->mightsee = kmalloc(bitbytes);
  801.     __bzero(SourcePortal->mightsee, bitbytes);
  802.     c_leafsee = 0;
  803.     /* SimpleFloof tags all the leafs, that SourcePortal might see. */
  804.     PortalThroughLeaf_3(SourcePortal, SourcePortal->leaf);
  805.     SourcePortal->nummightsee = c_leafsee;
  806.   }                                /* For each portal */
  807.  
  808. }
  809.  
  810. /*
  811.  * 2:
  812.  * This is the first modified version of baseportal vis.
  813.  * Some algoritmic improvements, based on the observation, that for i even, the
  814.  * points of the windings of portal i and i+1 are the same.
  815.  * It runs in approc 66-75% of the time the standard needs.
  816.  * 
  817.  */
  818. void BasePortalVis_2(void)
  819. {                                /* Faster then standard, one row, same result */
  820.   int i, j, k;
  821.   struct visportal *TestPortal, *SourcePortal;
  822.   float d;
  823.   struct winding *w;
  824.   bool TP1, TP2;
  825.  
  826.   /*
  827.    * For each global Portal, we check if it might be able to see TestPortal
  828.    * Information is stored in the portalsee array.
  829.    */
  830.   for (i = 0, SourcePortal = portals; i < numportals * 2; i++, SourcePortal++) {
  831.     c_portalsee = 0;                        /* This is how many other portals, p can see. */
  832.     __bzero(portalsee, numportals * 2);                /* We clear the array. */
  833.  
  834.     /*
  835.      * For each other portal, test if SourcePortal might be able to see it.
  836.      * Very loose bound. Front/Back
  837.      * Since the points of j and j+1 are the same, when j are even, some
  838.      * calculations can be spared. 
  839.      */
  840.     for (j = 0, TestPortal = portals;
  841.      j < numportals * 2;
  842.      j++, j++, TestPortal++, TestPortal++) {
  843.       if (i == j)                        /* This only catches i even, i=j and i=j+1 */
  844.     continue;
  845.       /* First, check if any point from TestPortal is in front of SourcePortal */
  846.       w = TestPortal->winding;
  847.       for (k = 0; k < w->numpoints; k++) {
  848.     d = DotProduct(w->points[k], SourcePortal->plane.normal) - SourcePortal->plane.dist;
  849.     if (d > ON_EPSILON)
  850.       break;
  851.       }
  852.       if (k == w->numpoints) {
  853.     /* Same points, so same test will fail. */
  854.     continue;                        /* no points on front */
  855.       }
  856.       /*
  857.        * If we reached here, for j = x, j even, then we are also
  858.        * going to reach this point for j = x + 1, since same points.
  859.        * And vice versa, the other way around. If we did NOT reach here,
  860.        * for j = x, j even, we are NOT going to get here for j = x + 1
  861.        * 
  862.        * Reaching this point, means that SourcePortal can see either
  863.        * TestPortal, or TestPortal++
  864.        */
  865.       /* Now check, if SourcePortal is behind TestPortal */
  866.       TP1 = TP2 = FALSE;
  867.       w = SourcePortal->winding;
  868.       for (k = 0; k < w->numpoints; k++) {
  869.     d = DotProduct(w->points[k], TestPortal->plane.normal) - TestPortal->plane.dist;
  870.     if (d < -ON_EPSILON)
  871.       TP1 = TRUE;
  872.     else if (d > ON_EPSILON)
  873.       TP2 = TRUE;
  874.     if (TP1 && TP2)
  875.       break;
  876.       }
  877.       if (TP1) {
  878.     portalsee[j] = 1;
  879.     c_portalsee++;
  880.       }
  881.       /* We never want to set the portal to see it self. */
  882.       if (i == j + 1)
  883.     continue;                        /* This catches the odd i's, with i == j */
  884.       /* Check, if SourcePortal is behind TestPortal++ */
  885.  
  886.       if (TP2) {
  887.     portalsee[j + 1] = 1;
  888.     c_portalsee++;
  889.       }
  890.     }                                /* End of TestPortal loop. */
  891.  
  892.     c_leafsee = 0;                        /* */
  893.     /* Allocate space for the mightsee array. Filled by SimpleFlood */
  894.     SourcePortal->mightsee = kmalloc(bitbytes);
  895.     __bzero(SourcePortal->mightsee, bitbytes);
  896.     /* SimpleFloof tags all the leafs, that SourcePortal might see. */
  897.     SimpleFlood(SourcePortal, SourcePortal->leaf);
  898.     SourcePortal->nummightsee = c_leafsee;
  899.   }
  900. }
  901.  
  902. /* This is the standard, but commented, version of BasePortalVis */
  903. void BasePortalVis_1(void)
  904. {                                /* Standard */
  905.   int i, j, k;
  906.   struct visportal *tp, *p;
  907.   float d;
  908.   struct winding *w;
  909.  
  910.   /* portals are the global portal array */
  911.   for (i = 0, p = portals; i < numportals * 2; i++, p++) {
  912.     p->mightsee = kmalloc(bitbytes);
  913.     __bzero(p->mightsee, bitbytes);
  914.  
  915.     /* portalsee is delared in this file. */
  916.     c_portalsee = 0;                        /* This is how many other portals, p can see. */
  917.     __bzero(portalsee, numportals * 2);                /* We clear the array. */
  918.  
  919.     for (j = 0, tp = portals; j < numportals * 2; j++, tp++) {
  920.       if (j == i)
  921.     continue;
  922.       w = tp->winding;
  923.       /*
  924.        * This for loop, apparently, checks if there is a point on the tp
  925.        * winding, that is in front of the p plane.
  926.        */
  927.       for (k = 0; k < w->numpoints; k++) {
  928.     d = DotProduct(w->points[k], p->plane.normal) - p->plane.dist;
  929.     if (d > ON_EPSILON)
  930.       break;
  931.       }
  932.       if (k == w->numpoints)
  933.     continue;                        /* no points on front */
  934.       /*
  935.        * The skipping here, must be because we have determined, that
  936.        * no points of the portal we checked against lies in 'the direction' in
  937.        * which we look.
  938.        *
  939.        * Same check for the other way around.
  940.        * No! This check must be for be for BEHIND!
  941.        */
  942.       w = p->winding;
  943.       for (k = 0; k < w->numpoints; k++) {
  944.     d = DotProduct(w->points[k], tp->plane.normal) - tp->plane.dist;
  945.     if (d < -ON_EPSILON)
  946.       break;
  947.       }
  948.       if (k == w->numpoints)
  949.     continue;                        /* no points on front <== Must be BACK! */
  950.  
  951.       /* If we reached this far, portal p (i) can se portal tp (j) */
  952.       portalsee[j] = 1;
  953.       c_portalsee++;
  954.  
  955.     }
  956.     c_leafsee = 0;                        /* */
  957.     SimpleFlood(p, p->leaf);
  958.     p->nummightsee = c_leafsee;
  959.   }
  960. }
  961. #endif
  962.  
  963. /*
  964.  * 
  965.  * Some textures (sky, water, slime, lava) are considered ambien sound emiters.
  966.  * Find an aproximate distance to the nearest emiter of each class for each leaf.
  967.  * 
  968.  */
  969.  
  970. /*
  971.  * ====================
  972.  * SurfaceBBox
  973.  * 
  974.  * ====================
  975.  */
  976. void SurfaceBBox(__memBase, register struct dface_t *s, register vec3_t mins, register vec3_t maxs)
  977. {
  978.   int i;
  979.   short int j;
  980.   int e;
  981.   int vi;
  982.   float *v;
  983.  
  984.   mins[0] = mins[1] = 999999;
  985.   maxs[0] = maxs[1] = -99999;
  986.  
  987.   for (i = 0; i < s->numedges; i++) {
  988.     e = bspMem->shared.quake1.dsurfedges[s->firstedge + i];
  989.     if (e >= 0)
  990.       vi = bspMem->shared.quake1.dedges[e].v[0];
  991.     else
  992.       vi = bspMem->shared.quake1.dedges[-e].v[1];
  993.     v = bspMem->shared.quake1.dvertexes[vi].point;
  994.  
  995.     for (j = 0; j < 3; j++) {
  996.       if (v[j] < mins[j])
  997.     mins[j] = v[j];
  998.       if (v[j] > maxs[j])
  999.     maxs[j] = v[j];
  1000.     }
  1001.   }
  1002. }
  1003.  
  1004. /*
  1005.  * ====================
  1006.  * CalcAmbientSounds
  1007.  * 
  1008.  * ====================
  1009.  */
  1010. void CalcAmbientSounds(__memBase)
  1011. {
  1012.   int i, j, k;
  1013.   short int l;
  1014.   struct dleaf_t *leaf, *hit;
  1015.   unsigned char *vis;
  1016.   struct dface_t *surf;
  1017.   vec3_t mins, maxs;
  1018.   float d, maxd;
  1019.   int ambient_type;
  1020.   struct texinfo *info;
  1021.   struct mipmap *miptex;
  1022.   int ofs;
  1023.   float dists[NUM_AMBIENTS];
  1024.   float vol;
  1025.  
  1026.   for (i = 0; i < num_visleafs; i++) {
  1027.     leaf = &bspMem->shared.quake1.dleafs[i + 1];
  1028.  
  1029.     /* clear ambients */
  1030.     for (j = 0; j < NUM_AMBIENTS; j++)
  1031.       dists[j] = 1020;
  1032.  
  1033.     vis = &uncompressed[i * bitbytes];
  1034.  
  1035.     for (j = 0; j < num_visleafs; j++) {
  1036.       if (!(vis[j >> 3] & (1 << (j & 7))))
  1037.     continue;
  1038.  
  1039.       /* check this leaf for sound textures */
  1040.       hit = &bspMem->shared.quake1.dleafs[j + 1];
  1041.  
  1042.       for (k = 0; k < hit->nummarksurfaces; k++) {
  1043.     surf = &bspMem->shared.quake1.dfaces[bspMem->shared.quake1.dmarksurfaces[hit->firstmarksurface + k]];
  1044.     info = &bspMem->shared.quake1.texinfo[surf->texinfo];
  1045.     ofs = ((struct dmiptexlump_t *)bspMem->shared.quake1.dtexdata)->dataofs[info->miptex];
  1046.     miptex = (struct mipmap *)(&bspMem->shared.quake1.dtexdata[ofs]);
  1047.  
  1048.     if (!strncasecmp(miptex->name, "sky", 3))
  1049.       ambient_type = AMBIENT_SKY;
  1050.     else if (!strncasecmp(miptex->name, "*slime", 6))
  1051.       ambient_type = AMBIENT_SLIME;                /* AMBIENT_SLIME; */
  1052.     else if (!strncasecmp(miptex->name, "*lava", 6))
  1053.       ambient_type = AMBIENT_LAVA;
  1054.     else if (miptex->name[0] == '*')
  1055.       ambient_type = AMBIENT_WATER;
  1056.     else
  1057.       continue;
  1058.  
  1059.     /* find distance from source leaf to polygon */
  1060.     SurfaceBBox(bspMem, surf, mins, maxs);
  1061.     maxd = 0;
  1062.     for (l = 0; l < 3; l++) {
  1063.       if (mins[l] > leaf->maxs[l])
  1064.         d = mins[l] - leaf->maxs[l];
  1065.       else if (maxs[l] < leaf->mins[l])
  1066.         d = leaf->mins[l] - mins[l];
  1067.       else
  1068.         d = 0;
  1069.       if (d > maxd)
  1070.         maxd = d;
  1071.     }
  1072.  
  1073.     maxd = 0.25;
  1074.     if (maxd < dists[ambient_type])
  1075.       dists[ambient_type] = maxd;
  1076.       }
  1077.     }
  1078.  
  1079.     for (j = 0; j < NUM_AMBIENTS; j++) {
  1080.       if (dists[j] < 100)
  1081.     vol = 1.0;
  1082.       else {
  1083.     vol = 1.0 - dists[2] * 0.002;
  1084.     if (vol < 0)
  1085.       vol = 0;
  1086.       }
  1087.       leaf->ambient_level[j] = vol * 255;
  1088.     }
  1089.     mprogress(num_visleafs, i + 1);
  1090.   }
  1091. }
  1092.  
  1093. /*============================================================================= */
  1094.  
  1095. /*
  1096.  * =============
  1097.  * GetNextPortal
  1098.  * 
  1099.  * Returns the next portal for a thread to work on
  1100.  * Returns the portals from the least complex, so the later ones can reuse
  1101.  * the earlier information.
  1102.  * =============
  1103.  */
  1104. struct visportal *GetNextPortal(void)
  1105. {
  1106.   int j;
  1107.   struct visportal *p, *tp;
  1108.   int min;
  1109.  
  1110.   min = 99999;
  1111.   p = NULL;
  1112.  
  1113.   /*
  1114.    * Finds the portal with the minimum mightsee number.
  1115.    * This operation is probably done quite a few times.
  1116.    * So maybe a data structure to update this information
  1117.    * would be appropiate? (min heap?)
  1118.    * Also, all portals are seeked. If there is no way a portal
  1119.    * can stop having status = stat_done, then it would be faster
  1120.    * to have another datastructure.
  1121.    */
  1122.   for (j = 0, tp = portals; j < num_visportals * 2; j++, tp++) {
  1123.     if (tp->nummightsee < min && tp->status == stat_none) {
  1124.       min = tp->nummightsee;
  1125.       p = tp;
  1126.     }
  1127.   }
  1128.  
  1129.   if (p)
  1130.     p->status = stat_working;
  1131.  
  1132.   return p;
  1133. }
  1134.  
  1135. /*
  1136.  * ===============
  1137.  * CompressRow
  1138.  * 
  1139.  * ===============
  1140.  */
  1141. int CompressRow(register unsigned char *vis, register unsigned char *dest)
  1142. {
  1143.   int j;
  1144.   int rep;
  1145.   int visrow;
  1146.   unsigned char *dest_p;
  1147.  
  1148.   dest_p = dest;
  1149.   visrow = (num_visleafs + 7) >> 3;
  1150.  
  1151.   for (j = 0; j < visrow; j++) {
  1152.     *dest_p++ = vis[j];
  1153.     if (vis[j])
  1154.       continue;
  1155.  
  1156.     rep = 1;
  1157.     for (j++; j < visrow; j++)
  1158.       if (vis[j] || rep == 255)
  1159.     break;
  1160.       else
  1161.     rep++;
  1162.     *dest_p++ = rep;
  1163.     j--;
  1164.   }
  1165.  
  1166.   return dest_p - dest;
  1167. }
  1168.  
  1169. /*
  1170.  * =============
  1171.  * SortPortals
  1172.  * 
  1173.  * Sorts the portals from the least complex, so the later ones can reuse
  1174.  * the earlier information.
  1175.  * =============
  1176.  */
  1177. /*
  1178.  * int PComp(register struct visportal *a, register struct visportal *b)
  1179.  * {
  1180.  * if (a->nummightsee == b->nummightsee)
  1181.  * return 0;
  1182.  * if (a->nummightsee < b->nummightsee)
  1183.  * return -1;
  1184.  * return 1;
  1185.  * }
  1186.  * 
  1187.  * void SortPortals(void)
  1188.  * {
  1189.  * heapsort(portals, num_visportals * 2, sizeof(struct visportal), PComp);
  1190.  * }
  1191.  */
  1192.  
  1193. /*
  1194.  * ===============
  1195.  * LeafFlow
  1196.  * 
  1197.  * Builds the entire visibility list for a leaf
  1198.  * ===============
  1199.  */
  1200. void LeafFlow(__memBase, register int leafnum)
  1201. {
  1202.   struct visleaf *leaf;
  1203.   unsigned char *outbuffer;
  1204.   unsigned char compressed[MAX_MAP_LEAFS / 8];
  1205.   int i, j;
  1206.   int numvis;
  1207.   struct visportal *p;
  1208.  
  1209.   /* flow through all portals, collecting visible bits */
  1210.   outbuffer = uncompressed + leafnum * bitbytes;
  1211.   /* Get a pointer to the leafnum leaf */
  1212.   leaf = leafs[leafnum];
  1213.   /* Iterate over all portals leaving this leaf. */
  1214.   for (i = 0; i < leaf->numportals; i++) {
  1215.     p = leaf->portals[i];
  1216.     if (p->status != stat_done)
  1217.       Error("portal not done\n");
  1218.     /* Or the leafs visible from this portal to the outbuffer */
  1219.     for (j = 0; j < bitbytes; j++)
  1220.       outbuffer[j] |= p->visbits[j];
  1221.   }
  1222.  
  1223.   /* Checks if the source leaf is visible from this leaf. */
  1224.   if (outbuffer[leafnum >> 3] & (1 << (leafnum & 7)))
  1225.     Error("Leaf portals saw into leaf\n");
  1226.  
  1227.   /* Writes the leaf itself to the visible array. */
  1228.   outbuffer[leafnum >> 3] |= (1 << (leafnum & 7));
  1229.  
  1230.   /* Collects statistical info. */
  1231.   numvis = 0;
  1232.   for (i = 0; i < num_visleafs; i++)
  1233.     if (outbuffer[i >> 3] & (1 << (i & 3)))
  1234.       numvis++;
  1235.  
  1236.   /* compress the bit string */
  1237.   if (bspMem->visOptions & VIS_VERBOSE)
  1238.     mprintf("----- leaf %4i ---------\n%5i visible\n", leafnum, numvis);
  1239.   totalvis += numvis;
  1240.  
  1241.   /* Compress the row to the "compressed" array. */
  1242.   i = CompressRow(outbuffer, compressed);
  1243.  
  1244.   if ((bspMem->shared.quake1.visdatasize + i) > bspMem->shared.quake1.max_visdatasize)
  1245.     ExpandClusters(bspMem, LUMP_VISIBILITY);
  1246.   memcpy(bspMem->shared.quake1.dvisdata + bspMem->shared.quake1.visdatasize, compressed, i);
  1247.   bspMem->shared.quake1.dleafs[leafnum + 1].visofs = bspMem->shared.quake1.visdatasize;        /* leaf 0 is a common solid */
  1248.   bspMem->shared.quake1.visdatasize += i;
  1249. }
  1250.  
  1251. /*
  1252.  * ==================
  1253.  * CalcPortalVis
  1254.  * ==================
  1255.  */
  1256. void CalcPortalVis(__memBase)
  1257. {
  1258.   int i;
  1259.   struct visportal *p;
  1260.  
  1261.   /* fastvis just uses mightsee for a very loose bound */
  1262.   if (bspMem->visOptions & VIS_FAST) {
  1263.     for (i = 0; i < num_visportals * 2; i++) {
  1264.       portals[i].visbits = portals[i].mightsee;
  1265.       portals[i].status = stat_done;
  1266.     }
  1267.     return;
  1268.   }
  1269.  
  1270.   leafon = 0;
  1271.  
  1272.   while ((p = GetNextPortal())) {
  1273.     PortalFlow(p);
  1274.     if (bspMem->visOptions & VIS_VERBOSE)
  1275.       mprintf("----- portal %4i -------\n %5i mightsee\n%5i cansee\n", (int)(p - portals), p->nummightsee, p->numcansee);
  1276.   }
  1277.  
  1278.   if (bspMem->visOptions & VIS_VERBOSE) {
  1279.     mprintf("%5i portalcheck\n%5i portaltest\n%5i portalpass\n", c_portalcheck, c_portaltest, c_portalpass);
  1280.     mprintf("%5i c_vistest\n%5i c_mighttest\n", c_vistest, c_mighttest);
  1281.   }
  1282.  
  1283. }
  1284.  
  1285. /*
  1286.  * ==================
  1287.  * CalcVis
  1288.  * ==================
  1289.  */
  1290. void CalcVis(__memBase)
  1291. {
  1292.   int i;
  1293.  
  1294.   switch (testvisfastlevel) {
  1295.     case 1:
  1296.       BasePortalVis_1();
  1297.       break;
  1298.     case 2:
  1299.       BasePortalVis_2();
  1300.       break;
  1301.     case 3:
  1302.       BasePortalVis_3();
  1303.       break;
  1304.     case 4:
  1305.       BasePortalVis_4();
  1306.       break;
  1307.     default:
  1308.       BasePortalVis_3();
  1309.       break;
  1310.   }
  1311.  
  1312.   /*SortPortals(); */
  1313.   CalcPortalVis(bspMem);
  1314.  
  1315.   /* assemble the leaf vis lists by oring and compressing the portal lists */
  1316.   for (i = 0; i < num_visleafs; i++) {
  1317.     LeafFlow(bspMem, i);
  1318.     mprogress(num_visleafs, i + 1);
  1319.   }
  1320.  
  1321.   mprintf("%5i average leafs visible\n", totalvis / num_visleafs);
  1322. }
  1323.  
  1324. /*
  1325.  * ==============================================================================
  1326.  * 
  1327.  * PASSAGE CALCULATION (not used yet...)
  1328.  * 
  1329.  * ==============================================================================
  1330.  */
  1331.  
  1332. bool PlaneCompare(register struct plane *p1, register struct plane *p2)
  1333. {
  1334.   int i;
  1335.  
  1336.   if (fabs(p1->dist - p2->dist) > 0.01)
  1337.     return FALSE;
  1338.  
  1339.   for (i = 0; i < 3; i++)
  1340.     if (fabs(p1->normal[i] - p2->normal[i]) > 0.001)
  1341.       return FALSE;
  1342.  
  1343.   return TRUE;
  1344. }
  1345.  
  1346. struct seperatingplane *Findpassages(register struct winding *source, register struct winding *pass)
  1347. {
  1348.   int i, j, k, l;
  1349.   struct plane plane;
  1350.   vec3_t v1, v2;
  1351.   float d;
  1352.   double length;
  1353.   int counts[3];
  1354.   bool fliptest;
  1355.   struct seperatingplane *sep, *list;
  1356.  
  1357.   list = NULL;
  1358.  
  1359.   /* check all combinations        */
  1360.   for (i = 0; i < source->numpoints; i++) {
  1361.     l = (i + 1) % source->numpoints;
  1362.     VectorSubtract(source->points[l], source->points[i], v1);
  1363.  
  1364.     /*
  1365.      * fing a vertex of pass that makes a plane that puts all of the
  1366.      * vertexes of pass on the front side and all of the vertexes of
  1367.      * source on the back side
  1368.      */
  1369.     for (j = 0; j < pass->numpoints; j++) {
  1370.       VectorSubtract(pass->points[j], source->points[i], v2);
  1371.  
  1372.       plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
  1373.       plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
  1374.       plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
  1375.  
  1376.       /* if points don't make a valid plane, skip it */
  1377.  
  1378.       length = plane.normal[0] * plane.normal[0]
  1379.     + plane.normal[1] * plane.normal[1]
  1380.     + plane.normal[2] * plane.normal[2];
  1381.  
  1382.       if (length < ON_EPSILON)
  1383.     continue;
  1384.  
  1385.       length = 1 / sqrt(length);
  1386.  
  1387.       plane.normal[0] *= length;
  1388.       plane.normal[1] *= length;
  1389.       plane.normal[2] *= length;
  1390.  
  1391.       plane.dist = DotProduct(pass->points[j], plane.normal);
  1392.  
  1393.       /*
  1394.        * find out which side of the generated seperating plane has the 
  1395.        * source portal
  1396.        */
  1397.       fliptest = FALSE;
  1398.       for (k = 0; k < source->numpoints; k++) {
  1399.     if (k == i || k == l)
  1400.       continue;
  1401.     d = DotProduct(source->points[k], plane.normal) - plane.dist;
  1402.     if (d < -ON_EPSILON) {                    /* source is on the negative side, so we want all */
  1403.       /* pass and target on the positive side */
  1404.  
  1405.       fliptest = FALSE;
  1406.       break;
  1407.     }
  1408.     else if (d > ON_EPSILON) {                /* source is on the positive side, so we want all */
  1409.       /* pass and target on the negative side */
  1410.  
  1411.       fliptest = TRUE;
  1412.       break;
  1413.     }
  1414.       }
  1415.       if (k == source->numpoints)
  1416.     continue;                        /* planar with source portal */
  1417.  
  1418.       /* flip the normal if the source portal is backwards */
  1419.       if (fliptest) {
  1420.     VectorNegate(plane.normal);
  1421.     plane.dist = -plane.dist;
  1422.       }
  1423.  
  1424.       /*
  1425.        * if all of the pass portal points are now on the positive side,
  1426.        * this is the seperating plane
  1427.        */
  1428.       counts[0] = counts[1] = counts[2] = 0;
  1429.       for (k = 0; k < pass->numpoints; k++) {
  1430.     if (k == j)
  1431.       continue;
  1432.     d = DotProduct(pass->points[k], plane.normal) - plane.dist;
  1433.     if (d < -ON_EPSILON)
  1434.       break;
  1435.     else if (d > ON_EPSILON)
  1436.       counts[0]++;
  1437.     else
  1438.       counts[2]++;
  1439.       }
  1440.       if (k != pass->numpoints)
  1441.     continue;                        /* points on negative side, not a seperating plane */
  1442.  
  1443.       if (!counts[0])
  1444.     continue;                        /* planar with pass portal */
  1445.  
  1446.       /* save this out */
  1447.       count_sep++;
  1448.  
  1449.       if (!(sep = (struct seperatingplane *)kmalloc(sizeof(struct seperatingplane))))
  1450.       Error(failed_memoryunsize, "seperate plane");
  1451.  
  1452.       sep->next = list;
  1453.       list = sep;
  1454.       sep->plane = plane;
  1455.     }
  1456.   }
  1457.  
  1458.   return list;
  1459. }
  1460.  
  1461. /*
  1462.  * ============
  1463.  * CalcPassages
  1464.  * ============
  1465.  */
  1466. void CalcPassages(void)
  1467. {
  1468.   int i, j, k;
  1469.   int count, count2;
  1470.   struct visleaf *l;
  1471.   struct visportal *p1, *p2;
  1472.   struct seperatingplane *sep;
  1473.   struct passage *passages;
  1474.  
  1475.   mprintf("    - building passages...\n");
  1476.  
  1477.   count = count2 = 0;
  1478.   for (i = 0; i < num_visleafs; i++) {
  1479.     l = leafs[i];
  1480.  
  1481.     for (j = 0; j < l->numportals; j++) {
  1482.       p1 = l->portals[j];
  1483.       for (k = 0; k < l->numportals; k++) {
  1484.     if (k == j)
  1485.       continue;
  1486.  
  1487.     count++;
  1488.     p2 = l->portals[k];
  1489.  
  1490.     /* definately can't see into a coplanar portal */
  1491.     if (PlaneCompare(&p1->plane, &p2->plane))
  1492.       continue;
  1493.  
  1494.     count2++;
  1495.  
  1496.     sep = Findpassages(p1->winding, p2->winding);
  1497.     if (!sep) {
  1498.       count_sep++;
  1499.       if (!(sep = (struct seperatingplane *)kmalloc(sizeof(struct seperatingplane))))
  1500.           Error(failed_memoryunsize, "seperate plane");
  1501.  
  1502.       sep->next = NULL;
  1503.       sep->plane = p1->plane;
  1504.     }
  1505.     if (!(passages = (struct passage *)kmalloc(sizeof(struct passage))))
  1506.         Error(failed_memoryunsize, "passage");
  1507.  
  1508.     passages->planes = sep;
  1509.     passages->from = p1->leaf;
  1510.     passages->to = p2->leaf;
  1511.     passages->next = l->passages;
  1512.     l->passages = passages;
  1513.       }
  1514.     }
  1515.   }
  1516.  
  1517.   mprintf("%5i numpassages (%i)\n", count2, count);
  1518.   mprintf("%5i total passages\n", count_sep);
  1519. }
  1520.  
  1521. /*============================================================================= */
  1522.  
  1523. bool vis(__memBase, int level, char *prtBuf)
  1524. {
  1525.   int i;
  1526.  
  1527.   mprintf("----- Vis ---------------\n");
  1528.  
  1529.   AllocClusters(bspMem, LUMP_VISIBILITY);
  1530.  
  1531.   if (!(bspMem->visOptions & VIS_MEM))
  1532.     LoadPortals(prtBuf);
  1533.   if (level)
  1534.     testvislevel = level;
  1535.  
  1536.   originalvismapsize = num_visportals * ((num_visportals + 7) / 8);
  1537.   bitbytes = ((num_visportals + 63) & ~63) >> 3;
  1538.   bitlongs = bitbytes / sizeof(long long int);
  1539.  
  1540.   if (!(uncompressed = (unsigned char *)kmalloc(bitbytes * num_visleafs)))
  1541.     Error(failed_memoryunsize, "bitbytes");
  1542.  
  1543.   mprintf("----- CalcVis -----------\n");
  1544. /*CalcPassages (); */
  1545.   CalcVis(bspMem);
  1546.  
  1547.   mprintf("%5i c_chains\n", c_chains);
  1548.   mprintf("%5i visdatasize (compressed from %i)\n", bspMem->shared.quake1.visdatasize, originalvismapsize);
  1549.  
  1550.   mprintf("----- CalcAmbientSounds -\n");
  1551.   CalcAmbientSounds(bspMem);
  1552.  
  1553.   for (i = 0; i < num_visleafs; i++)
  1554.     if (leafs[i])
  1555.       FreeLeaf(leafs[i]);
  1556.   for (i = 0; i < (num_visportals * 2); i++)
  1557.     if (portals[i].winding);
  1558.   FreeWinding(portals[i].winding);
  1559.   tfree(leafs);
  1560.   tfree(portals);
  1561.   kfree();
  1562.  
  1563.   return TRUE;
  1564. }
  1565.